﻿//给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
//
//你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
//
//你可以按任意顺序返回答案。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/two-sum
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。



class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        int left = 0;
        int right = nums.size() - 1;
        while (left < right)
        {
            if (nums[left] + nums[right] != target)
            {
                int flag = 0;
                int tmp = left + 1;
                while (tmp < right)
                {
                    if (nums[tmp] + nums[right] == target)
                    {
                        left = tmp;
                        flag = 1;
                        break;
                    }
                    ++tmp;
                }
                if (flag)
                {
                    continue;
                }
                tmp = right - 1;
                while (tmp > left)
                {
                    if (nums[left] + nums[tmp] == target)
                    {
                        right = tmp;
                        flag = 1;
                        break;
                    }
                    --tmp;
                }
                if (flag)
                {
                    continue;
                }
                left++;
                right--;

            }
            else
            {
                ret.push_back(left);
                ret.push_back(right);
                break;
            }
        }
        return ret;
    }
};


//哈希表更快

vector<int> ret;
unordered_map<int, int> hmap;

for (int i = 0; i < nums.size();++i)  //遍历数组
{
    std::unordered_map<int, int>::iterator it = hmap.find(target - nums[i]);
    if (it != hmap.end())
    {
        ret.push_back(it->second);
        ret.push_back(i);
        break;
    }
    hmap[nums[i]] += i;
}

return ret;